#include<stdio.h>
#include<stdlib.h>
//data 和 next next指向下一个的date

typedef int ElemType;


typedef struct node//此处的node为标签，在自引用中需要这个标签，如果不用的话，里面的改成Node不行，因为这个程序还没执行完，识别不了Node
{//c中，结构体变量不能包含自身实例，会无限递归，但可以包含指向本身的指针。使用指针加*来声明next,且表示其next为一个指针
	ElemType data;
	struct node* next;//node 类型的结构体本身，相当于存了下一个链表（节点）的地址.尾节点的那个next一定是null
}Node;//别名

//struct node{};node n1  错,少了struct
//typedef struct node{}Node;Node n1   对

Node* initList()//初始化且创造了一个头节点        initi为一个函数，返回类型为Node*指针，加*（该函数需要返回一个指向链表头节点的指针）。   这里用Node*是函数返回的是一个指向Node结构的指针
{
	//下面的head加*是因为它是一个指向Node结构体的指针
	Node* head = (Node*)malloc(sizeof(Node));//相当于在堆内存创造了一个结构体head指针
	head->data = 0;
	head->next = NULL;
	return head;
}
int insertHead(Node* L, ElemType e)
{
	Node* p = (Node*)malloc(sizeof(Node));//创建一个新的节点
	p->data = e;//把数据赋予这个新节点的数据域上
	p->next = L->next;//先让新的这个节点地址指向原来头节点指向的那个位置
	L->next = p;//然后再让头节点的地址指向新节点
	return 1;
}
void listNode(Node* L)//遍历，传进来一个链表
{
	Node* p = L->next;//第一个节点，不是头节点
	while (p != NULL)
	{
		printf("%d\n", p->data);
		p = p->next;
	}
	printf("\n");
}
int main02()//头插法，插在头节点的后面
{
	Node* list = initList();
	insertHead(list, 10);
	insertHead(list, 20);
	insertHead(list, 30);
	listNode(list);
	return 0;
	//头插法输出的跟输入的顺序是相反的
}








//尾插法，得先获取尾节点的地址
Node* get_tail(Node* L)
{
	Node* p = L;
	while (p->next != NULL)
	{
		p = p->next;
	}
	return p;
}
Node* insertTail(Node* tail, ElemType e)
{
	Node* p = (Node*)malloc(sizeof(Node));
	p->data = e;
	tail->next = p;
	p->next = NULL;
	return p;//返回的是新的节点
}
int main03()
{
	Node* list = initList();
	Node* tail = get_tail(list);
	tail = insertTail(tail, 10);
	tail = insertTail(tail, 20);
	tail = insertTail(tail, 30);
	listNode(list);//遍历要从头节点开始，即list
	return 0;
}













/*                在指定位置插入                        */
int insertNode(Node* L, int pos, ElemType e)
{
	Node* p = L; //用*p指向这个链表,用来保存插入位置的前驱节点
	int i = 0;
	while (i < pos - 1)//循环这个列表，循环到需要的位置的前一个
	{
		p = p->next;//p就是传进来的链表
		i++;
		if (p == NULL)//传进来的是头节点
		{
			return 0;
		}
	}
	Node* q = (Node*)malloc(sizeof(Node));//要插入的新节点 
	q->data = e;
	q->next = p->next;
	p->next = q;
	return 1;
}
int main04()
{
	Node* list = initList();
	Node* tail = get_tail(list);
	tail = insertTail(tail, 10);
	tail = insertTail(tail, 20);
	tail = insertTail(tail, 30);
	listNode(list);
	insertNode(list, 2, 15);
	listNode(list);
	return 0;
}








/*                删除指定节点                        */
//找到要删除节点的前置位置
//用指针q记录要删除的节点，即创建一个q
//通过改变P的后继节点实现删除（这里的P指要删除的节点的前一个节点）
//释放节点的空间
int deleteNode(Node* L, int pos)
{
	Node* p = L;//要删除节点的前驱
	int i = 0;
	//遍历链表，找到要删除节点的前驱,下面的p就在pos的前一个
	while (i < pos - 1)
	{
		p = p->next;
		i++;
		if (p == NULL)
		{
			return 0;
		}
	}
	if (p->next == NULL)
	{
		printf("要删除的位置错位\n");
		return 0;
	}
	//让q指向要删除的那个节点  
	Node* q = p->next;
	//让要删除节点的前驱指向要删除节点的后继
	p->next = q->next;
	free(q);
	return 1;
}
int main05()
{
	Node* list = initList();
	Node* tail = get_tail(list);
	tail = insertTail(tail, 10);
	tail = insertTail(tail, 20);
	tail = insertTail(tail, 30);
	listNode(list);
	insertNode(list, 2, 15);
	listNode(list);
	deleteNode(list, 2);
	listNode(list);
	return 0;
}









/*获取链表的长度*/
int listLength(Node* L)
{
	Node* p = L;
	int len = 0;
	while (p != NULL)
	{
		p = p->next;
		len++;
	}
	return len;
}
int main()
{
	Node* list = initList();
	Node* tail = get_tail(list);
	tail = insertTail(tail, 10);
	tail = insertTail(tail, 20);
	tail = insertTail(tail, 30);
	listNode(list);
	insertNode(list, 2, 15);
	listNode(list);
	deleteNode(list, 2);
	listNode(list);
	printf("%d", listLength(list));//这里包括了头节点
	return 0;
}

